P3426 [POI2005]SZA-Template 题解

结论题可爱

题意简述

给出一个字符串 ，你可以使用一个印章，每次能印出一个相同的字符串 ，印章印过的地方可以重叠，但是重叠部分的字符必须相同。求最小的印章长度，。

思路分析及证明

首先可以想到 。设 代表恰好覆盖 的长度为 的前缀 所需要的最小的印章长度。

通过尝试，我们容易发现如下引理。

引理0：若 能够恰好覆盖 ， 能够恰好覆盖 ，则 能恰好覆盖 。

证明：构造一个映射即可，结论显然。

引理1：若 且 能够恰好覆盖 ， 一定能恰好覆盖 的最长公共前后缀。

证明：设 的最长公共前后缀长度为 。分类讨论。

• 若 ，由于必然存在第一次印章使得 被印出，又必然存在最后一次印章使得 被印出，而 ，所以这两段合并后一定能够覆盖一个完整的 。
• 若 ，则必然存在前若干次印章恰好印出 ，使得 ；同时，必然存在后若干次印章恰好印出 使得 。而 ，即 ，所以这两段合并后一定能够覆盖一个完整的 。

综上，引理1得证。

因此，我们发现 能够转移过来的状态其实很少。接下来，我们聚焦于 。

引理2：若 都能够恰好覆盖（），则 能够恰好覆盖 。

证明：分类讨论。

• 若 ，结论显然成立。
• 否则，根据引理1，我们知道 都能恰好覆盖 的最长公共前后缀。若 最长公共前后缀为 ，则不存在两个不同的印章使得 能够被恰好覆盖。所以， 的最长公共前后缀不为 。那么可以得到： 都能够恰好覆盖（）。又根据引理1， 都能够恰好覆盖 。显然， 一定会在某次迭代中出现。又由于同时有两个不为串长的印章可以覆盖该串，所以在 出现前引理1一直成立。不断迭代下去，直到 同时能够恰好覆盖的串变为 。此时，我们推出 都能够恰好覆盖 ，即待证结论。

综上，引理2得证。

引理3： 的取值只能为 或 。

证明： 显然可能取到。我们着重讨论 。

首先根据引理1， 一定能够恰好覆盖 。又因为 代表能够恰好覆盖 的最小值，所以 。那么，如果 是合法的转移，我们一定会优先选取 。

接下来讨论 不合法的情况（即 不能恰好覆盖 ）。设 ，且 是一个合法的转移（即 能够恰好覆盖 ）。根据引理2， 都能够恰好覆盖 ，则 能够恰好覆盖 。又根据引理0， 能够恰好覆盖 ，即 合法，矛盾，即不存在这样的 。

因此，我们得到如下结论：

• 若 合法，则一定选取。
• 否则，没有转移方案， 只能取到 。

综上，引理3得证。

接下来，我们考虑如何检验 的合法性。注意到我们可以直接以 为结尾印出一个 的串，检验能否从前面已经处理过的状态衔接过来就好了。直观感知到应该从一个状态 使得 转移，接下来进行详细证明。

引理4： 可以取到 （），当且仅当存在 。

证明：

• 对于 的状态，显然合法。

• 对于 的状态，一定是无法进行转移的，因为 的过程是一个单调不降的过程。

• 对于 的状态，假设 是一个合法的状态，则 必须能够恰好覆盖 。而能够恰好覆盖 的最小长度是 ，故推出矛盾。

综上，引理4得证。

至此，我们就做完了这道题。直抒胸臆，酣畅淋漓！

开一个桶存储一下最大的 值为某个特定值的位置，验证其是否 即可判断合法性。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include<bits/stdc++.h>
using namespace std;
int dp[500005],n,r[500005],nxt[500005];
char s[500005];
void KMP(){
	for(int i=2;i<=n;i++){
		int k=nxt[i-1];
		while(k&&s[k+1]!=s[i]) k=nxt[k];
		if(s[k+1]==s[i]) k++;
		nxt[i]=k;
	}
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	KMP();
	dp[1]=1;
	r[1]=1;//桶
	for(int i=2;i<=n;i++){
		dp[i]=i;
		if(nxt[i]&&r[dp[nxt[i]]]>=i-dp[nxt[i]]) dp[i]=dp[nxt[i]];
		r[dp[i]]=i;
	}
	cout<<dp[n];
	return 0;
}